In many information processing systems having a number of system resources, often called servers, the situation frequently arises wherein a set of requesters must arbitrate for service from one of a number of servers. For instance, in a data packet switching application, the requesters may each need to transmit one or more cells (i.e., small packets of information) to various ones of the servers. Each requester receives cells from one or more system users (e.g., components) that need to be forwarded to specified ones of the servers. If the requester has at least one cell that needs to be forwarded to a server, then the requester will generate a request for access. The problem is to rapidly produce a set of one-to-one matchings that maximizes the number of connections between requesters and servers. Preferably the matchings should be produced without imposing significant overhead on the system.
Switching (i.e., connecting requesters to servers, or transmitting data from senders to receivers) involves two separate tasks. First, a scheduling task is performed, wherein an arbitration mechanism selects which of potentially many requests to send to each server. Second, a data forwarding task is performed, in which a switching mechanism forwards requests or cells to servers in accordance with the selections made by the scheduling task.
Such an arbitration mechanism may be needed in contexts other than data packet switching. For instance, a computer system may have multiple processors that must be matched (or selectively coupled) to multiple storage units ("servers"). The requesters generate access requests to ones of the storage units, which requests are presented to an arbitration mechanism. The arbitration mechanism first selects which requests to grant, and then an interconnection or switching mechanism couples the selected processors to the requested storage units.
Although the subsequent material herein describes a local area switching network, the present invention may be applied in any application in which a rapid matching of requestors and servers is needed. Referring to FIG. 1, in a point-to-point communications network 10, the network has a number of switches 12 each of which is connected to other switches and/or a number of hosts (H), such as workstations. Each switch 12 has multiple input ports through which "requesters" generate requests, and multiple output ports or "servers". Cells of data are presented to the input ports of the switch via link circuitry. Each input port receives, and stores in an input buffer, a set of cells, with each cell member bearing an address that identifies an output port to which the cell requests routing. The arbitration mechanism now must satisfy not one request, but a set of requests. This is a relatively difficult and time consuming task because many arbitration matches are possible between cells in the input port sets and the output ports. Some matches will be better than others, and the problem is to rapidly find a good match satisfying the largest number of contending requests.
Ideally, the arbitration mechanism will rapidly provide a "maximum match", a match having the property that no other arrangement between input ports and output ports would make more requester-server connections possible. Unfortunately assuring and achieving a maximum match within a relatively short number of clock cycles is computationally very difficult and is not necessarily feasible in a practical application.
A less ideal but more realizable solution is for the arbitration mechanism to provide a "maximal match", a match having the property that once matching is complete no additional connections ports can be made. However in a maximal match, if it were permissible to subsequently rearrange connections and priorities, additional connections might in fact be possible.
The present invention is an arbitration mechanism and procedure that provides maximal matching within a relatively small number of clock cycles. Fast matching is important so that the arbitration procedure can be repeated quickly for successive sets of requests. In particular, the arbitration procedure for one set of requests should be no longer than the amount of time needed to transmit the requests granted during the previous arbitration cycle. When the requests are small cells that are transmitted in just a few clock cycles, the arbitration mechanism has only a similar number of clock cycles to arbitrate competing requests. The arbitration mechanism of the present invention can be implemented using presently existing circuit components.